package org.example.code.test2025.one_month;

import java.math.BigInteger;
import java.util.*;

/**
 * @Title: test0103
 * @Author yxy
 * @Package org.example.code.test2025.one_month
 * @Date 2025/1/3 10:01
 * @description:
 */
public class test0103 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates);
        fun(candidates,res,new ArrayList<Integer>(),target,0);
        return res;
    }

    private void fun(int[] candidates, List<List<Integer>> res, ArrayList<Integer> cur, int target,int start) {
        if (countList(cur) == target) {
            res.add(new ArrayList<>(cur));
            return;
        }
        if(countList(cur)>target) {
            return;
        }
        for(int i=start;i<candidates.length;i++) {
            if(i>start&&candidates[i]==candidates[i-1]) {
                continue;
            }
            cur.add(candidates[i]);
            fun(candidates,res,cur,target,i+1);
            cur.remove(cur.size()-1);
        }
    }

    private int countList(ArrayList<Integer> cur) {
        int sum = 0;
        for (Integer i : cur) {
            sum += i;
        };
        return sum;
    }

    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);

        for(int i=0;i<nums.length-3;i++) {
            if(i>0&&nums[i]==nums[i-1]) {
                continue;
            }
            for (int j=i+1;j<nums.length-2;j++) {
                if(j>i+1&&nums[j]==nums[j-1]) {
                    continue;
                }
                int left = j+1,right = nums.length-1;
                while(left<right) {
                    long sum = (long) nums[i]+nums[j]+nums[left]+nums[right];
                    if(sum==target) {
                        res.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        left++;
                        right--;
                    }else if(sum>target) {
                        right--;
                    }else {
                        left++;
                    }
                }
            }
        }
        return res;
    }

    public String multiply(String num1, String num2) {

        BigInteger bigNum1 = new BigInteger(num1);
        BigInteger bigNum2 = new BigInteger(num2);

        BigInteger result = bigNum1.multiply(bigNum2);
        return result.toString();
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        Arrays.sort(nums);
        funPermuteUnique(nums,res,new ArrayList<Integer>(),used);
        return res;
    }

    private void funPermuteUnique(int[] nums, List<List<Integer>> res, ArrayList<Integer> cur, boolean[] used) {
        if(cur.size()==nums.length) {
            res.add(new ArrayList<>(cur));
            return;
        }
        for(int i=0;i<nums.length;i++) {
            if(used[i]) {
                continue;
            }
            if(i>0&&nums[i]==nums[i-1]&&!used[i-1]) {
                continue;
            }
            cur.add(nums[i]);
            used[i] = true;
            funPermuteUnique(nums,res,cur,used);
            used[i] = false;
            cur.remove(cur.size()-1);
        }
    }

    public static void main(String[] args) {
//        System.out.println(new test0103().combinationSum2(new int[]{2,5,2,1,2}, 5));
        test0103 test = new test0103();
//        List<List<Integer>> res = test.fourSum(new int[]{1000000000,1000000000,1000000000,1000000000}, -294967296);
//        System.out.println(res);
//        System.out.println(test.multiply("100", "100"));
        System.out.println(test.permuteUnique(new int[]{1, 1, 3}));
    }
}
